import java.util.ArrayList;
import java.util.List;

public class Num89 {
    //格雷编码}
    //回溯算法
//    List<Integer> res;
//    public List<Integer> grayCode(int n) {
//        int len = (int)Math.pow(2,n);
//        List<Integer> path = new ArrayList<>();
//        dfs(path,0,len);
//        return res;
//    }
//
//    private void dfs(List<Integer> path, int depth, int len) {
//        if (depth == len) {
//            if (res != null) return;
//            int num1 = path.get(0);
//            int num2 = path.get(len - 1);
//            if (towPow(num1,num2)) {
//                res = new ArrayList<>(path);
//            }
//            return;
//        }
//        for (int i = 0; i < len; i++) {
//            if (path.contains(i)) continue;
//            if (path.size() == 0) {
//                path.add(i);
//                dfs(path,depth + 1,len);
//                path.remove(0);
//            }else if (towPow(path.get(path.size() - 1),i)) {
//                path.add(i);
//                dfs(path,depth + 1,len);
//                path.remove(path.size() - 1);
//            }else continue;
//        }
//    }
//
//    private boolean towPow(int num1, int num2) {
//        int n = 0;
//        while (num1 != 0 || num2 != 0) {
//            if (num1 % 2 != num2 % 2) n++;
//            num1 = num1 >> 1;
//            num2 = num2 >> 1;
//        }
//        return n == 1 ? true : false;
//    }
    //归纳法
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        int head = 1;
        for (int i = 0; i < n; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                res.add(head + res.get(j));
            }
            head = head << 1;
        }
        return res;
    }
}
